COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00005 ENDMK
C⊗;
\input macro[1,mps]
\input macrwf[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm B03.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, December 18, 1989}
\leftline{\sevenrm Unpublished draft}
\bigskip
\centerline {\bf Mini-Final Exam, CS254, Fall 1989}
\medskip
(1)  Let $M↓1$ be an oblivious Turing machine (no input or output devices,
any storage device you like).  Let $H$ be the set of programs for $M↓1$ that
have a complete computation (``half'').  Let $M↓2$ be a TM with input and
output, and $M↓{2H}$ be that TM with an oracle for $H$.  Which of these sets
can be generated by a program for $M↓{2H}$:

\item\item{(A)} The programs for $M↓2$ that halt on some input

\item\item{(B)} The programs for $M↓2$ that halt on no input

\item\item{(C)} The programs for $M↓2$ that halt on all inputs

\item\item{(D)} The programs for $M↓2$ that do not halt on all inputs.

(2)

\item\item{(A)} Show that if a decision problem is in $P$ (deterministic
polynomial time) on a two-stack machine, then it is in $P$ in a one-queue
machine, and conversely.

\item\item{(B)} Show that there is a decision problem that is in $P$ on a two-stack
machine but not on a multi-counter machine.

(3)

\item\item{(A)} Show that the set of composite numbers, as written in binary notation,
is in NP.

\item\item{(B)} Show that the set of composite numbers, as written in unary
notation ($n$ is represented by $n\, 1's$) is in $P$.

\item\item{(4)} Show that the set of locally constrained symbol systems (LCSS) that
have more than one solution is NP-complete.

Each numbered problem is worth 10 points.  Your grade will be based on your
three best scores, so three {\it correct} solutions is plenty.
\end